#include "ListNode.h"

class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode *addInList(ListNode *head1, ListNode *head2)
    {
        if (head1 == nullptr)
        {
            return head2;
        }
        if (head2 == nullptr)
        {
            return head1;
        }
        ListNode *r1 = reverse(head1);
        ListNode *r2 = reverse(head2);
        ListNode *virtual_head = new ListNode(-1);
        ListNode *p = virtual_head;
        int jin = 0, sum = 0;
        while (r1 || r2)
        {
            if (r1 != nullptr && r2 != nullptr)
            {
                sum = r1->val + r2->val + jin;
                r1 = r1->next;
                r2 = r2->next;
            }
            else if (r1 != nullptr)
            {
                sum = r1->val + jin;
                r1 = r1->next;
            }
            else
            {
                sum = r2->val + jin;
                r2 = r2->next;
            }
            jin = sum / 10;
            p->next = new ListNode(sum % 10);
            p = p->next;
        }
        if (jin > 0)
        {
            p->next = new ListNode(jin % 10);
        }
        return reverse(virtual_head->next);
    }

    ListNode *reverse(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode *pre = nullptr;
        while (head)
        {
            ListNode *next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};